/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <sys/stat.h>
#include <iostream>
#include <fcntl.h>

using namespace std;

BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    this -> mode = mode;
    if (pf.open(indexname, mode) != 0) {
	return RC_FILE_OPEN_FAILED;
    }
    if (mode == 'w') {
	return 0;
    }
    char buffer[PageFile::PAGE_SIZE];

    if (pf.read(0, buffer) != 0) {
	return RC_FILE_READ_FAILED;
    }
    char* offset = &(buffer[0]);
    memcpy(&rootPid, offset, sizeof(PageId));
    memcpy(&treeHeight, (offset + sizeof(PageId)), sizeof(int));

return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	char buffer[PageFile::PAGE_SIZE];
	char* offset = &(buffer[0]);
	if (mode == 'w') {
		memset(offset, 0, PageFile::PAGE_SIZE);
		memcpy(offset, &rootPid, sizeof(PageId));
		memcpy(offset + sizeof(PageId), &treeHeight, sizeof(PageId));
		if (pf.write(0, buffer) != 0) {
			return RC_FILE_WRITE_FAILED;
		}
	}
return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{	
	int midKey;
	PageId oPid;
	PageId nPid;
	BTLeafNode leaf;
	BTNonLeafNode sib;
	BTNonLeafNode node;
	IndexCursor cursor;

	if (treeHeight == 1) {
		leaf.read(cursor.pid, pf);
		if (leaf.insert(key, rid) != 0) {
			goto split;
		}
		leaf.write(cursor.pid, pf);
		return 0;
	}
	if (leaf.insert(key, rid) != 0) {
	split:
		int sKey;
		BTLeafNode sibling;
		leaf.insertAndSplit(key, rid, sibling, sKey);
		PageId nextNodePtr = leaf.getNextNodePtr();
		sibling.setNextNodePtr(nextNodePtr);
		leaf.setNextNodePtr(pf.endPid());
		
		if (leaf.write(cursor.pid, pf) != 0) {
			return RC_FILE_WRITE_FAILED;
		}
		if (sibling.write(pf.endPid(), pf) != 0) {
			return RC_FILE_WRITE_FAILED;
		}
		if (treeHeight == 1) {
			BTNonLeafNode root;
			root.initializeRoot(cursor.pid, sKey, pf.endPid()-1);
			if (root.write(pf.endPid(), pf) != 0) {
				return RC_FILE_WRITE_FAILED;
			}
			rootPid = pf.endPid() - 1;
			treeHeight++;
			return 0;
		}
		int i = 0;
		do {
			oPid = nPid;
			list.getTailValue(nPid);
			
			if (node.read(nPid, pf) != 0) {
				return RC_FILE_READ_FAILED;
			}
			
			if (i == 0) {
				if (node.insert(sKey, pf.endPid()-1) == 0) {
					if (node.write(nPid, pf) != 0) {
						return RC_FILE_WRITE_FAILED;
					}
					break;
				} else {
					node.insertAndSplit(sKey, cursor.pid, sib, midKey);
					sib.write(pf.endPid(), pf);
					if (node.write(nPid, pf) != 0) {
						return RC_FILE_WRITE_FAILED;
					}
				}
			} else {
				if (node.insert(midKey, oPid) == 0) {
					if (node.write(nPid, pf) != 0) {
						return RC_FILE_WRITE_FAILED;
					}
					break;
				} else {
					node.insertAndSplit(midKey, oPid, sib, midKey);
					sib.write(pf.endPid(), pf);		
					if (nPid == rootPid) {
						BTNonLeafNode root;
						root.initializeRoot(nPid, midKey, pf.endPid()-1);
						if(root.write(pf.endPid(), pf) != 0) {
							return RC_FILE_WRITE_FAILED;
						}
						rootPid = pf.endPid() - 1;
						treeHeight++;
					}
					if (node.write(nPid, pf) != 0) {
						return RC_FILE_WRITE_FAILED;
					}
					break;
				}
			}
			i++;
		} while (nPid != rootPid);
	}
	if (leaf.write(cursor.pid, pf) != 0) {
		return RC_FILE_WRITE_FAILED;
	}
	list.destructList();
	
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
	if (treeHeight == 0) {
		rootPid = 1;
		cursor.pid = 1;
		cursor.eid = 0;
		treeHeight++;

	} else if (treeHeight == 1) {
		BTLeafNode root;
		int eid;
		if (root.locate(searchKey, eid) != 0) {
			return RC_NO_SUCH_RECORD;
		}
		if (root.read(rootPid, pf) != 0) {
			return RC_FILE_READ_FAILED;
		}
		cursor.pid = rootPid;
		cursor.eid = eid;
	} else {
		BTNonLeafNode node;
		if (node.read(rootPid, pf) != 0) {
			return RC_FILE_READ_FAILED;
		}
		int level = 1;
		while (level < treeHeight) {
			if (level == 1) {
				list.insert(rootPid);
			} else {
				list.insert(nextPid);
			}
			if(node.locateChildPtr(searchKey, nextPid) != 0) {
				return RC_NO_SUCH_RECORD;
			}
			if (node.read(nextPid, pf) != 0) {
				return RC_FILE_READ_FAILED;
			}
			level++;
		}
		cursor.pid = nextPid;
		cursor.eid = 0;
	}
return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
	BTLeafNode node;
	if (node.readEntry(cursor.eid, key, rid) != 0) {
		return RC_INVALID_RID;
	}	
	if (node.read(cursor.pid, pf) != 0) {
		return RC_FILE_READ_FAILED;
	}
	if (cursor.eid < node.getKeyCount() - 1) {
		cursor.eid++;
	} else {
		cursor.eid = 0;
		int next;
		next = node.getNextNodePtr();
		if (next == 0) {
			return RC_END_OF_TREE;
		}
		cursor.pid = next;
	}
return 0;
}

Node::Node(PageId pid) { this->pid = pid; }

PageId Node::getPid() { return this->pid; }

LinkedList::LinkedList() {
	head = tail = 0;
	length = 0;
}

int LinkedList::insert(PageId pid) {
	if (length == 0) {
		head = new Node(pid);
		tail = head;
		tail->next = 0;
		head->prev = 0;
		length == 1;
	} else {
		Node* temp = new Node(pid);
		tail->next = temp;
		temp->next = 0;
		temp->prev = tail;
		tail = temp;
		length++;
	}
	return 0;
}

int LinkedList::getTailValue(PageId& pid) {
	pid = tail->pid;
	Node* temp;
	if (tail->prev) {
		temp = tail->prev;
	} else {
		return -1;
	}
	delete tail;
	tail = temp;
	return 0;
}

int LinkedList::destructList() {
	while (head != tail) {
		Node* temp = tail->prev;
		delete tail;
		tail = temp;
	}
	delete head;
	
return 0;
}
